#leetcode题目287：寻找重复数
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)

#使用快慢指针，快指针每次走两步，慢指针每次走一步，如果有环，则快慢指针会相遇


from typing import List
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        """
        寻找重复数
        给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），
        可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，返回这个重复的数。
        
        使用弗洛伊德判圈算法（Floyd's Cycle Detection Algorithm）
        将数组看作链表，nums[i] 表示从位置 i 指向位置 nums[i]
        """
        slow = 0
        fast = 0
        
        # 第一阶段：找到快慢指针的相遇点
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        
        # 第二阶段：找到环的入口点（重复数）
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow



#测试数据
nums = [1,3,4,2,2]
#预期输出：2
solution = Solution()
print(solution.findDuplicate(nums))

nums = [3,1,3,4,2]
#预期输出：3
solution = Solution()
print(solution.findDuplicate(nums))

nums = [3,3,3,3,3]
#预期输出：3
solution = Solution()
print(solution.findDuplicate(nums))